package everydayone.mySqrt;

/**
 * @Date 2020/05/09
 * @author 王光浩
 * @Thinking 使用二分法
 * @Analysis 时间复杂度O（logn），空间复杂度O（1）
 */
public class MyMethodTwo {
	public int mySqrt(int x) {
		if (x <= 0)
			return x;
		long l = 0;
		long r = x;
		long mid;
		while (l < r) {
			mid = l + (r - l) / 2;
			if (mid * mid >= x)
				r = mid;
			else
				l = mid + 1;
		}
		return r * r > x ? (int) r - 1 : (int) r;
	}
}
